	#include<sstream>
	#include <string>
	#include <stack>
	#include <map>
	#include <deque>
	#include <string>
	#include <string.h>
	#include <vector>
	#include <set>
	#include <algorithm>
	#include <list>

	using namespace std;

	class regExprHandler  
	{
	protected:
		class expState
		{
		protected:
			multimap<char, expState*> transitionContainer;
			int m_nStateID;
			set<expState*> statesNFA;

		public:
			expState() : m_nStateID(-1), acceptingState_(false) {};
			expState(int nID) : m_nStateID(nID), acceptingState_(false) {};
			expState(set<expState*> NFAState, int nID)
			{
				statesNFA			= NFAState;
				m_nStateID			= nID;
				acceptingState_	= false;
				set<expState*>::iterator iter;
				for(iter=NFAState.begin(); iter!=NFAState.end(); ++iter)
					if((*iter)->acceptingState_)
						acceptingState_ = true;
			};

			expState(const expState &other)
			{ *this = other; };
			virtual ~expState() {};
			bool acceptingState_;
			void AddTransition(char chInput, expState *pState)
			{
				transitionContainer.insert(make_pair(chInput, pState));
			};
			void RemoveTransition(expState* pState)
			{
				multimap<char, expState*>::iterator iter;
				for(iter=transitionContainer.begin(); iter!=transitionContainer.end();)
				{
					expState *toState = iter->second;
					if(toState == pState)
						transitionContainer.erase(iter++);
					else ++iter;
				}
			};
			void GetTransition(char chInput, vector<expState*> &States)
			{
				States.clear();
				multimap<char, expState*>::iterator iter;
				for(iter = transitionContainer.lower_bound(chInput);
					iter!= transitionContainer.upper_bound(chInput);
					++iter)
					{
						expState *pState = iter->second;
						States.push_back(pState);
					}
			};
			string GetStateID()
			{
				string strRes;
				stringstream s;
				
				s << m_nStateID;
				if(acceptingState_)
				{
					strRes = "{";
					strRes += s.str() ;
					strRes = "}";
				}
				else
				{
					strRes += s.str() ;
				}
				
				return strRes;
				
			};

			set<expState*>& GetNFAState()
			{ return statesNFA; };
			bool IsDeadEnd()
			{
				if(acceptingState_)
					return false;
				if(transitionContainer.empty())
					return true;
				multimap<char, expState*>::iterator iter;
				for(iter=transitionContainer.begin(); iter!=transitionContainer.end(); ++iter)
				{
					expState *toState = iter->second;
					if(toState != this)
						return false;
				}
				return true;
			};	
			expState& operator=(const expState& other)
			{ 
				transitionContainer	= other.transitionContainer; 
				m_nStateID		= other.m_nStateID;
				statesNFA		= other.statesNFA;
				return *this;
			};
			bool operator==(const expState& other)
			{
				if(statesNFA.empty())
					return(m_nStateID == other.m_nStateID);
				else return(statesNFA == other.statesNFA);
			};
		};
		class CAG_PatternState
		{
		public:
			CAG_PatternState() : m_pState(NULL), m_nStartIndex(-1) {};
			CAG_PatternState(const CAG_PatternState &other)
			{ *this = other; };
			virtual ~CAG_PatternState() {};
			expState* m_pState;
			int m_nStartIndex;
			CAG_PatternState& operator=(const CAG_PatternState& other)
			{
				m_pState		= other.m_pState;
				m_nStartIndex	= other.m_nStartIndex;
				return *this;
			};
		};

		typedef deque<expState*> FSA_TABLE;
		FSA_TABLE m_NFATable;
		FSA_TABLE m_DFATable;
		stack<FSA_TABLE> m_OperandStack;
		stack<char> m_OperatorStack;
		int m_nNextStateID;
		set<char> m_InputSet;
		list<CAG_PatternState*> m_PatternList;
		int m_nPatternIndex;
		string m_strText;
		vector<string> m_vecPattern;
		vector<int> m_vecPos;
		void Push(char chInput);
		bool Pop(FSA_TABLE &NFATable);
		bool IsOperator(char ch) { return((ch == 42) || (ch == 124) || (ch == 40) || (ch == 41) || (ch == 8)); };
		bool Presedence(char opLeft, char opRight)
		{
			if(opLeft == opRight)
				return true;
			if(opLeft == '*')
				return false;
			if(opRight == '*')
				return true;
			if(opLeft == 8)
				return false;
			if(opRight == 8)
				return true;
			if(opLeft == '|')
				return false;
			return true;
		};
		bool IsInput(char ch) { return(!IsOperator(ch)); };
		bool IsLeftParanthesis(char ch) { return(ch == 40); };
		bool IsRightParanthesis(char ch) { return(ch == 41); };
		bool Eval();
		bool Concat();
		bool Star();
		bool Union();
		string ConcatExpand(string strRegEx);
		bool CreateNFA(string strRegEx);
		void EpsilonClosure(set<expState*> T, set<expState*> &Res); 
		void Move(char chInput, set<expState*> T, set<expState*> &Res);
		void ConvertNFAtoDFA();
		void ReduceDFA();
		void CleanUp()
		{
			for(int i=0; i<m_NFATable.size(); ++i)
				delete m_NFATable[i];
			m_NFATable.clear();
			for(int i=0; i<m_DFATable.size(); ++i)
				delete m_DFATable[i];
			m_DFATable.clear();
			m_nNextStateID = 0;
			while(!m_OperandStack.empty())
				m_OperandStack.pop();
			while(!m_OperatorStack.empty())
				m_OperatorStack.pop();
			m_InputSet.clear();
			list<CAG_PatternState*>::iterator iter;
			for(iter=m_PatternList.begin(); iter!=m_PatternList.end(); ++iter)
				delete *iter;
			m_PatternList.clear();
		};
		bool Find();
	public:
		regExprHandler();
		virtual ~regExprHandler();
		bool SetRegEx(string strRegEx);
		bool FindFirst(string strText, int &nPos, string &strPattern);
		bool FindNext(int &nPos, string &strPattern);
	};
